package com.mgq.algorithm.dp;

/**
 * 有n个打包机器从左到右一字排开，. 上方有一个自动装置会抓取一批放物品到每个打
 * 包机上，放到每个机器上的这些物品数量有多有少，由于物品数量不相同，需要工人
 * 将每个机器上的物品进行移动从而到达物品数量相等才能打包。每个物品重量太大、
 * 每次只能搬一个物品进行移动，为了省力，只在相邻的机器上移动。请计算在搬动最
 * 小轮数的前提下，使每个机器上的物品数量相等。如果不能使每个机器上的物品相同，
 * 返回-1。
 * 例如[1, 0, 5]表示有3个机器，每个机器上分别有1、0、5个物品，经过这些轮后:
 * 第一-轮:1 0<-5 =>1 1 4第二轮:1<-1<-4=>2 1 3第三轮:
 * 2 1 <-3 =>2 2 2
 * 移动了3轮，每个机器上的物品相等，所以返回3
 * 例如[2, 2, 3]表示有3个机器，每个机器上分别有2、2、3个物品，
 * 这些物品不管怎么移动，都不能使三个机器上物品数量相等，返回-1
 * 洗衣机问题
 */
public class Wash {
    public static int wash(int[] array) {
        if (array == null || array.length == 0) {
            return -1;
        }
        int sum=0;
        for (int i = 0; i < array.length; i++) {
            sum += array[i];
        }
        int N = array.length;
        if (sum % N != 0) {
            return -1;
        }
        int avg = sum / N;
        //左侧已经遍历过的累加和
        int leftSum=0;
        int result=0;
        for (int i = 0; i < array.length; i++) {
            //左侧需要甩出的衣服 (左侧累加和-左侧需要的衣服数量) 负,表示外界输入衣服, 正表示需要往外输出
            int leftRest = leftSum - i * avg;
            //右侧需要甩出的衣服  (右侧衣服的实际数量 - 右侧需要的衣服数量)
            int rightRest = (sum-leftSum-array[i]) - ((N-i-1) * avg);
            System.out.println("leftRest:"+leftRest+" ,rightRest:"+rightRest);
            //左负右负 相加
            if (leftRest < 0 && rightRest < 0) {
                result = Math.max(result, Math.abs(leftRest) + Math.abs(rightRest));
            } else {
                //取绝对值的最大值
                result = Math.max(result,Math.max(Math.abs(leftRest),Math.abs(rightRest)));
            }
            leftSum += array[i];
        }
        return result;
    }

    public static void main(String[] args) {
        wash(new int[]{100, 0, 0, 0});
    }
}
